package com.ycz.algorithm.utils.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author yancz
 * @ClassName ArrayBinaryTree
 * @description: 基于数组实现的二叉树
 * @date 2024-12-19 11:28:02
 * @version: 1.0
 */
public class ArrayBinaryTree {

    private List<Integer> tree;

    // 构造方法
    public ArrayBinaryTree(List<Integer> arr) {
        tree = new ArrayList<>(arr);
    }

    // 列表容量
    public int size() {
        return tree.size();
    }

    // 获取索引为i的节点值
    public Integer getValue(int i) {
        if (i < 0 || i >= size()) {
            return null;
//            throw new IndexOutOfBoundsException("索引越界！");
        }
        return tree.get(i);
    }

    // 获取索引为i的节点的左节点索引
    public Integer getLeftIndex(int i) {
        return 2 * i + 1;
    }

    // 获取索引为i的节点的右节点索引
    public Integer getRightIndex(int i) {
        return 2 * i + 2;
    }

    // 获取索引为i的节点的父节点索引
    public Integer getParentIndex(int i) {
        return (i - 1) / 2;
    }

    /*
     * @author yancz
     * @description 层序遍历
     * @date 2024/12/19 11:37
     * @return List<Integer>
     **/
    public List<Integer> levelOrder() {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < size(); i++) {
            if (getValue(i) != null) {
                list.add(getValue(i));
            }
        }
        return list;
    }

    /*
     * @author yancz
     * @description 深度优先遍历
     * @date 2024/12/19 11:56
     * @param i 索引
     * @param order 遍历方式
     * @param list 收集遍历节点值的容器

     **/
    private void depthFirst(Integer i, String order, List<Integer> list) {
        if (getValue(i) == null) {
            return;
        }
        Integer value = getValue(i);
        if ("pre".equals(order)) { // 前序遍历，先加值，再递归左子树、右子树
            list.add(value);
        }
        depthFirst(getLeftIndex(i), order, list);
        if ("mid".equals(order)) { // 中序遍历，先递归左子树后加值，最后递归右子树
            list.add(value);
        }
        depthFirst(getRightIndex(i), order, list);
        if ("next".equals(order)) { // 后序遍历，递归完左子树、右子树，最后再加值
            list.add(value);
        }
    }

    // 前序遍历
    private List<Integer> preOrder() {
        List<Integer> list = new ArrayList<>();
        depthFirst(0, "pre", list);
        return list;
    }

    // 中序遍历
    private List<Integer> midOrder() {
        List<Integer> list = new ArrayList<>();
        depthFirst(0, "mid", list);
        return list;
    }

    // 后序遍历
    private List<Integer> nextOrder() {
        List<Integer> list = new ArrayList<>();
        depthFirst(0, "next", list);
        return list;
    }

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(list);
        List<Integer> arrs = arrayBinaryTree.levelOrder();
        System.out.println("层序遍历：");
        for (Integer i : arrs) {
            System.out.print(i + "\t");
        }
        System.out.println();
        arrs = arrayBinaryTree.preOrder();
        System.out.println("先序遍历：");
        for (Integer i : arrs) {
            System.out.print(i + "\t");
        }
        System.out.println();
        arrs = arrayBinaryTree.midOrder();
        System.out.println("中序遍历：");
        for (Integer i : arrs) {
            System.out.print(i + "\t");
        }
        System.out.println();
        arrs = arrayBinaryTree.nextOrder();
        System.out.println("后序遍历：");
        for (Integer i : arrs) {
            System.out.print(i + "\t");
        }
    }

}
